package algorithm_diagram;

import java.util.*;

//广度优先搜索，解决两个问题，是否有从A到B的路径，查找从A到B的最短路径。运行时间为V+E，V为顶点数，E为边数。属于贪心（贪婪）算法一种。
//树是图的子集，拓部结构也是图的子集。有向图关系单向，无向图关系双向。
// 最短路径的搜索列表必须是队列；对于搜索过的元素，务必不再搜索，否则可能导致无线循环。
public class BreadthFirstSearch {

    private static Map<String, List<String>> map= new HashMap<>();

    public static void main(String[] args) {
        map.put("you", Arrays.asList("alice", "bob", "claire"));
        map.put("bob", Arrays.asList("anuj", "peggy"));
        map.put("alice", Arrays.asList("peggy"));
        map.put("claire", Arrays.asList("thom", "jonny"));
        map.put("anuj", Collections.emptyList());
        map.put("peggy", Collections.emptyList());
        map.put("thom", Collections.emptyList());
        map.put("jonny", Collections.emptyList());
        breadthFirstSearch("you");
    }

    //搜索关系链中关系最近的芒果供应商
    private static void breadthFirstSearch(String name){
        Queue<String> queue = new ArrayDeque<>(map.get(name));
        ArrayList<String> list = new ArrayList<>();
        while(!queue.isEmpty()){
            String ele = queue.poll();//从队列中删除获取第一个元素匹配
            if(!list.contains(ele)){//搜索过的元素不再搜索
                if(ele.endsWith("m")){
                    System.out.println(ele+"是芒果供应商");
                }else{
                    queue.addAll(map.get(ele));//将该元素邻居添加到队列
                    list.add(ele);
                }
            }
        }
    }
}
